/**
 * Created with IntelliJ IDEA
 * Description Java实现将中缀表达式转换为逆波兰式
 * User: 王杰
 * Date: 2025-05-10
 * Time: 9:15
 */
import java.util.Stack;
import java.util.EmptyStackException;
import java.util.Scanner;

public class InfixToPostfix {

    // 检查字符是否为运算符
    private static boolean isOperator(char c) {
        return c == '+' || c == '-' || c == '*' || c == '/' || c == '^';
    }

    // 获取运算符优先级
    private static int precedence(char op) {
        switch (op) {
            case '+':
            case '-': return 1;
            case '*':
            case '/': return 2;
            case '^': return 3;
            default: return 0;
        }
    }

    // 检查字符是否为操作数组成部分
    private static boolean isOperandChar(char c) {
        return Character.isDigit(c) || c == '.' || Character.isLetter(c);
    }

    // 检查是否是有效的变量名(单字母)
    private static boolean isValidVariable(String s) {
        return s.length() == 1 && Character.isLetter(s.charAt(0));
    }

    // 严格检查是否是有效的数字(包含小数)
    private static boolean isValidNumber(String s) {
        if (s.startsWith(".")) return false;  // 不能以小数点开头
        if (s.endsWith(".")) return false;  // 不能以小数点结尾
        if (s.indexOf('.') != s.lastIndexOf('.')) return false;  // 不能有多个小数点

        try {
            Double.parseDouble(s);
            return true;
        } catch (NumberFormatException e) {
            return false;
        }
    }

    // 中缀转后缀主方法
    public static String infixToPostfix(String infix) throws IllegalArgumentException {
        StringBuilder postfix = new StringBuilder();
        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < infix.length(); i++) {
            char c = infix.charAt(i);

            // 跳过空格
            if (c == ' ') continue;

            // 如果是操作数(数字、小数点或字母)
            if (isOperandChar(c)) {
                StringBuilder operand = new StringBuilder();
                // 收集完整的操作数(数字或变量)
                while (i < infix.length() && isOperandChar(infix.charAt(i))) {
                    operand.append(infix.charAt(i));
                    i++;
                }
                i--; // 回退一格，因为for循环会自增

                String operandStr = operand.toString();
                // 检查是数字还是变量
                if (isValidVariable(operandStr)) {
                    // 单字母变量
                    postfix.append(operandStr).append(' ');
                } else if (isValidNumber(operandStr)) {
                    // 有效数字
                    postfix.append(operandStr).append(' ');
                } else {
                    throw new IllegalArgumentException("非法数字格式 '" + operandStr + "'，位置: " + (i - operandStr.length() + 1));
                }
            }
            // 如果是左括号，压栈
            else if (c == '(') {
                stack.push(c);
            }
            // 如果是右括号，弹出栈顶元素直到遇到左括号
            else if (c == ')') {
                while (!stack.isEmpty() && stack.peek() != '(') {
                    postfix.append(stack.pop()).append(' ');
                }

                if (stack.isEmpty()) {
                    throw new IllegalArgumentException("不匹配的右括号，位置: " + i);
                }

                stack.pop(); // 弹出左括号但不输出
            }
            // 如果是运算符
            else if (isOperator(c)) {
                while (!stack.isEmpty() && precedence(c) <= precedence(stack.peek())) {
                    postfix.append(stack.pop()).append(' ');
                }
                stack.push(c);
            }
            else {
                throw new IllegalArgumentException("非法字符 '" + c + "'，位置: " + i);
            }
        }

        // 弹出栈中剩余的所有运算符
        while (!stack.isEmpty()) {
            if (stack.peek() == '(') {
                throw new IllegalArgumentException("不匹配的左括号");
            }
            postfix.append(stack.pop()).append(' ');
        }

        return postfix.toString().trim();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.println("中缀表达式转逆波兰式(后缀表达式)");
        System.out.println("输入表达式(输入q退出):");

        while (true) {
            System.out.print("> ");
            String input = scanner.nextLine().trim();

            if (input.equalsIgnoreCase("q")) {
                break;
            }

            try {
                String postfix = infixToPostfix(input);
                System.out.println("逆波兰式: " + postfix);
            } catch (IllegalArgumentException e) {
                System.out.println("错误: " + e.getMessage());
            } catch (EmptyStackException e) {
                System.out.println("错误: 表达式处理过程中栈异常");
            }
        }

        scanner.close();
        System.out.println("程序结束");
    }
}